package Array;

/**
 * 55. 跳跃游戏
 *  给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

 解题思路： 基于 45题目的思路，贪心思想
    我们要判断是否能达到最后一个位置， 那么就要统计当前位置上能够达到的最远距离 和 i位置上下一步能够达到的最远距离
    通过实时更新 maxJump 和 nextMaxJump，来判断是否能到达最后一个位置
 解题步骤：
    1：定义变量，maxJump 和 nextMaxJump，分别记录当前位置能跳到的最远距离 和 i位置下一步能够跳到的最远距离 ， 从首位开始，所以初始值，maxJump = nums[0], nextMaxJump = 0 + nums[0]
    2: 遍历数组，如果i位置 大于 当前位置记录的maxJump，证明i位置调不到，则直接返回false
    3： 实时更新nextMaxJump，记录下一步能够跳到的最远距离， 取 nextMaxJump 与 i+nums[i] 的最大值，代表下一步能够跳到的最远距离
    4： 如果i位置等于当前最大位置maxJump，则更新maxJump为nextMaxJump

 总结： 跳跃问题是一个累加问题，实时取最大值并作出判断，不能陷入比较相邻元素的错误思路，时刻使用贪心思路，每一步都要考虑局部最优解。
 */
public class CanJump {

    public boolean canJump(int[] nums) {
        int maxJump = nums[0];  // 记录当前位置能跳到的最远距离
        int nextMaxJump = 0 + nums[0]; // 记录下一次能跳到的最远距离
        for (int i = 1; i < nums.length ; i++) {
            // i位置大于了当前位置能跳到的最大距离，所以返回false
            if(i > maxJump){
                return false;
            }
            // 更新下一次能够跳到的最远距离
            nextMaxJump = Math.max(nextMaxJump,i + nums[i]);
            // 如果到达了maxJump，则更新maxJump为下一次能跳到的最远距离
            if(i == maxJump){
                maxJump = nextMaxJump;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        CanJump canJump = new CanJump();
        System.out.println(canJump.canJump(nums));
    }


    /**
     *  解题思路： 力扣思路
     *     首先要明白题意，只有到达当前元素，才能判断下一次跳几步（基于当前元素的值），所以我们可以记录每次跳的最远距离是否满足条件。
     *     使用贪心思路解决问题，因为要尽可能地跳到最远的位置，所以我们需要比较当前位置上能跳到的最远距离，
     *    每次取 i+num[i] 的值就是当前位置能跳到的最远距离，然后再与之前能跳到的最远距离比较，取最大值，实时更新最远距离，是否符合条件.
     *  解题步骤：
     *     1:定义一个变量 maxJump 记录从起点位置到当前位置前能跳到的最远距离，初始值是0
     *     2:遍历数组,判断当前位置 i 是否大于最大距离，如果大于，则返回false，否则返回true
     *     3:计算当前位置能跳到的最远距离，取当前位置能跳到的最远距离和之前能跳到的最远距离的较大值，更新maxJump
     * @param nums
     * @return
     */

    public boolean canJump1(int[] nums) {
        int maxJump = 0;
        for (int i = 0; i < nums.length; i++){
            // 如果当前位置大于能跳到的最大距离，则返回false
            if( i > maxJump){
                return false;
            }
            maxJump = Math.max(maxJump,i + nums[i]);
        }
        return true;
    }


}
